package mo.offer_special;

import java.util.HashMap;
import java.util.Map;

public class L017 {

    private Map<Character, Integer> ori = new HashMap<>();
    private Map<Character, Integer> cnt = new HashMap<>();

    public String minWindow(String s, String t) {
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0)+1);
        }
        int l = 0;
        int r = -1;
        int ansL = -1;
        int ansR = -1;
        int len = Integer.MAX_VALUE;
        int sLength = s.length();
        int valid = 0;
        while (r < sLength) {
            r++;
            if (r < sLength && ori.containsKey(s.charAt(r))) {
                char c = s.charAt(r);
                int count = cnt.getOrDefault(s.charAt(r), 0)+1;
                cnt.put(c, count);
                if (count == ori.get(s.charAt(r))) {
                    valid++;
                }
            }

            while (cnt.size() >= ori.size() && valid == ori.size() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                char c = s.charAt(l);
                int oriCount = ori.getOrDefault(c, 0);
                if (oriCount > 0) {
                    int cntCount = cnt.getOrDefault(c, 0);
                    if (oriCount == cntCount) {
                        valid--;
                    }
                    cnt.put(c, cntCount-1);
                }
                l++;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);

    }

}
